#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <map>
#include <deque>

using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
		int len = nums.size();
		int sum = nums[0] + nums[1] + nums[2];
		if(len == 3){
			return sum;
		}
		sort(nums.begin(), nums.end());
		// for(auto i : nums){
			// cout << i << " ";
		// }
		// cout << endl;
		for(int i = 0; i < len-2; i++){
			int left = i + 1;
			int right = len - 1;
			while(left < right){
				int tmp = nums[i] + nums[left] + nums[right];
				if(target - tmp == 0){
					return target;
				}
				if(abs(target - sum) > abs(target - tmp)){
					sum = tmp;
				}
				if(tmp < target){
					left++;
					// while(nums[left] == nums[left+1] && left < len-2){
						// left++;
					// }
				}
				if(tmp > target){
					right--;
					// while(nums[right] == nums[right-1] && right > i + 2){
						// right--;
					// }
				}
			}
		}
		return sum;
    }
};

int main(){
	Solution so;
	vector<int> input = {-1, 2, 1, -4};
	int a = so.threeSumClosest(input, 1);
	cout << "res:" << a << endl;;
	return 0;
}